package com.itheima.leetcode.od.b.backtracking;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * (C卷,200分)- 信道分配（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 算法工程师小明面对着这样一个问题 ，需要将通信用的信道分配给尽量多的用户:
 * <p>
 * 信道的条件及分配规则如下:
 * <p>
 * 所有信道都有属性:”阶”。阶为 r的信道的容量为 2^r比特;
 * 所有用户需要传输的数据量都一样:D比特;
 * 一个用户可以分配多个信道，但每个信道只能分配给一个用户;
 * 只有当分配给一个用户的所有信道的容量和>=D，用户才能传输数据;
 * 给出一组信道资源，最多可以为多少用户传输数据?
 * <p>
 * 输入描述
 * <p>
 * 第一行，一个数字 R。R为最大阶数。
 * <p>
 * 0<=R<20
 * <p>
 * 第二行，R+1个数字，用空格隔开。代表每种信道的数量 Ni。按照阶的值从小到大排列。
 * <p>
 * 0<=i<=R,0<=Ni<1000.
 * <p>
 * 第三行，一个数字 D。D为单个用户需要传输的数据量。
 * <p>
 * 0<D<1000000
 * <p>
 * 输出描述
 * <p>
 * 一个数字（代表最多可以供多少用户传输数据）
 * <p>
 * 用例
 * <p>
 * 输入	5
 * 10 5 0 1 3 2
 * 30
 * 输出	4
 * 说明	无
 */
public class ChannelAllocation {
    public static void main(String[] args) {
        /*Scanner in = new Scanner(System.in);

        // 读取第一行输入
        int temp2 = Integer.parseInt(in.nextLine().trim());

        // 读取第二行输入并转换为整数数组
        String[] rListStr = in.nextLine().trim().split(" ");
        int[] rList = new int[rListStr.length];
        for (int i = 0; i < rListStr.length; i++) {
            rList[i] = Integer.parseInt(rListStr[i]);
        }

        // 读取第三行输入
        int inputTemp = Integer.parseInt(in.nextLine().trim());*/

        int temp2 = 5;
        int[] rList = Arrays.stream("10 5 0 1 3 2".split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        int inputTemp = 30;

        System.out.println(getResult(rList, inputTemp));
    }

    /**
     * 球视角的回溯（组合总和无重复），装满的最大桶数
     *
     * @param rList
     * @param inputTemp
     * @return
     */
    public static int getResult(int[] rList, int inputTemp) {

        int mNumber = 0; // 超过 30 的信道数目
        LinkedList<Integer> balls = new LinkedList<Integer>();
        for (int i = rList.length - 1; i >= 0; i--) {
            for (int j = 0; j < rList[i]; j++) {
                int cap = (int) Math.pow(2, i);
                if (cap < inputTemp) { // 大于 30 的直接算一个桶
                    balls.addLast(cap);
                } else {
                    mNumber++;
                }
            }
        }

        int sum = balls.stream().reduce(Integer::sum).orElse(0);

        // 假设每个桶刚好装满不多不少 向下取整就是最多能填满的最大桶数
        int m = sum / inputTemp;
        while (m > 0) {
            if (check(0, balls, new int[m], inputTemp)) {
                return m + mNumber;
            }
            m--;
        }

        return mNumber;
    }

    private static boolean check(int index, LinkedList<Integer> balls, int[] buckets, int inputTemp) {
        // 如果balls已经取完，且桶都 >= 最低要求
        if (buckets.length == Arrays.stream(buckets)
                .boxed()
                .filter(integer -> integer >= inputTemp)
                .count()) {
            return true;
        }

        if (index == balls.size()) {
            return false;
        }

        // select是当前要装的球
        int selected = balls.get(index);

        // 遍历桶
        for (int i = 0; i < buckets.length; i++) {
            // 剪枝优化
            if (i > 0 && buckets[i] == buckets[i - 1]) { // 除去重复的组合情况 带入球的视角很关键
                continue;
            }

            int weight = buckets[i];
            int remain = inputTemp - weight;

            if (0 >= remain) {
                continue;
            }

            buckets[i] += selected;
            // 递归装下一个球
            if (check(index + 1, balls, buckets, inputTemp)) {
                return true;
            }
            // 如果这种策略无法装完所有球，则回溯
            buckets[i] -= selected;
        }

        return false;
    }
}